Endogenous Macrodynamics in Algorithmic Recourse

IEEE Conference on Secure and Trustworthy Machine Learning

Delft University of Technology

Giovan Angela
Aleksander Buszydlik
Karol Dobiczek
Arie van Deursen
Cynthia C. S. Liem

February 3, 2023

Background

  • Counterfactual Explanation (CE) explain how inputs into a model need to change for it to produce different outputs.
  • Counterfactual Explanations that involve realistic and actionable changes can be used for the purpose of Algorithmic Recourse (AR) to help individuals who face adverse outcomes.

Example: Consumer Credit

In Figure 1, arrows indicate changes from factuals (credit denied) to counterfactuals (credit supplied).

Figure 1: Counterfactuals for Give Me Some Credit dataset (Kaggle 2011).

Our work in a nutshell …

[…] we run experiments that simulate the application of recourse in practice using various state-of-the-art counterfactual generators and find that all of them induce substantial domain and model shifts.

Figure 2 illustrates how the application of recourse can induce shifts.

Figure 2: Dynamics in Algorithmic Recourse.

Proof-of-Concept

In Figure 3, a retail bank has trained binary classifier to evaluate credit applicants. Credit risk is highest in bottom-right corner.

Figure 3: Dynamics in Algorithmic Recourse.

In Figure 4, the retail bank has provided recourse to some of the previously unsuccessful applicants. We observe an endogenous domain shift.

Figure 4: Dynamics in Algorithmic Recourse.

In Figure 5, the retail bank has retrained the classifier. We consider this as an endogenous model shift.

Figure 5: Dynamics in Algorithmic Recourse.

Figure 6 shows the outcome after the process has been repeated a few times.

Figure 6: Dynamics in Algorithmic Recourse.

Questions?

Who is supposed to carry the risk (cost)? Also, what have we really achieved? Individuals who received recourse are easily distinguishable, hence subject to discrimination.

Research Questions

Principal Concerns

RQ 1 (Endogenous Shifts) Does the repeated implementation of recourse provided by state-of-the-art generators lead to shifts in the domain and model?

RQ 2 (Costs) If so, are these dynamics substantial enough to be considered costly to stakeholders involved in real-world automated decision-making processes?

RQ 3 (Heterogeneity) Do different counterfactual generators yield significantly different outcomes in this context? Furthermore, is there any heterogeneity concerning the chosen classifier and dataset?

RQ 4 (Drivers) What are the drivers of endogenous dynamics in Algorithmic Recourse?

Secondary Concerns

RQ 5 (Mitigation Strategies) What are potential mitigation strategies with respect to endogenous macrodynamics in AR?

Gradient-Based Recourse Revisited

From Individual Recourse …

Many existing approaches to CE and AR work with the following baseline:

\[ \begin{aligned} \mathbf{s}^\prime &= \arg \min_{\mathbf{s}^\prime \in \mathcal{S}} \left\{ {\text{yloss}(M(f(\mathbf{s}^\prime)),y^*)}+ \lambda {\text{cost}(f(\mathbf{s}^\prime)) } \right\} \end{aligned} \qquad(1)\]

Typically concern has centred around minimizing costs to a single individual.

… towards collective recourse

We propose to extend Equation 1 as follows:

\[ \begin{aligned} \mathbf{s}^\prime &= \arg \min_{\mathbf{s}^\prime \in \mathcal{S}} \{ {\text{yloss}(M(f(\mathbf{s}^\prime)),y^*)} \\ &+ \lambda_1 {\text{cost}(f(\mathbf{s}^\prime))} + \lambda_2 {\text{extcost}(f(\mathbf{s}^\prime))} \} \end{aligned} \qquad(2)\]

  • Here \(\text{cost}(f(\mathbf{s}^\prime))\) denotes the proxy for private costs faced by the individual; the newly introduced term \(\text{extcost}(f(\mathbf{s}^\prime))\) is meant to capture external costs generated by changes to \(\mathbf{s}^\prime\).
  • We borrow the concept of Negative Externalities from Economics (see more detailed slide pack)

Illustrating the trade-off

Experiments

Empirical Setup

  • Evaluation metrics: propose various metrics to measure domain shifts (MMD) and model shifts (MMD, parameter perturbations, disagreement coefficient, …)
  • Models: we use linear classifiers, deep neural networks and deep ensembles.
  • Data: we look at synthetic and real-world datasets:
    • Four synthetic datasets: Overlapping, Linearly Separable, Circles and Moons (Figure 7).
    • Three real-world datasets from the Finance and Economics domain: Give Me Some Credit (Kaggle 2011), UCI defaultCredit (Yeh and Lien 2009) and California Housing Pace and Barry (1997).

Figure 7: Synthetic classification datasets used in our experiments. Samples from the negative class (\(y=0\)) are marked in orange while samples of the positive class (\(y=1\)) are marked in blue.

Principal Findings

Results for synthetic data.

Results for real-world data.

Mitigation Strategies

  • More Conservative Decision Thresholds
  • Classifier Preserving ROAR (ClaPROAR)1:

\[ \begin{aligned} \text{extcost}(f(\mathbf{s}^\prime)) = l(M(f(\mathbf{s}^\prime)),y^\prime) \end{aligned} \qquad(3)\]

  • Gravitational Counterfactual Explanations:

\[ \begin{aligned} \text{extcost}(f(\mathbf{s}^\prime)) = \text{dist}(f(\mathbf{s}^\prime),\bar{x}^*) \end{aligned} \qquad(4)\]

Mitigation strategies.

Secondary Findings

Results for synthetic data.

Results for real-world data.

Discussion

Key Takeaways 🔑

  • State-of-the-art approaches to AR induce substantial domain and model shifts.
  • External costs of Individual Recourse should be shared across stakeholders.
  • Straightforward way to achieve this is to explicitly penalize external costs in the counterfactual search objective function (Equation 2).

Future Research Ideas

Private vs. External Costs:

  • How can we make informed choices about the tradeoff between private and external costs?
  • Pareto-optimal collective recourse?

Causal Modelling:

  • How do things play out for recent approaches to AR that incorporate causal knowledge such as Karimi, Schölkopf, and Valera (2021)?

Counterfactual Explanations and Probabilistic Machine Learning

We are working on methodologies and open-source tools to help researchers and practitioners assess the trustworthiness of predictive models.

Towards Trustworthy AI in Julia

  1. CounterfactualExplanations.jl (JuliaCon 2022)
  2. ConformalPrediction.jl (JuliaCon 2023 — I hope!)
  3. LaplaceRedudx.jl (JuliaCon 2022)
  4. AlgorithmicRecourseDynamics.jl

… contributions welcome! 😊

More Reading

Image Sources

  • Copyright for stock images belongs to TU Delft.
  • All other images, graphics or animations were created by us.

References

Joshi, Shalmali, Oluwasanmi Koyejo, Warut Vijitbenjaronk, Been Kim, and Joydeep Ghosh. 2019. “Towards Realistic Individual Recourse and Actionable Explanations in Black-Box Decision Making Systems.” https://arxiv.org/abs/1907.09615.
Kaggle. 2011. “Give Me Some Credit, Improve on the State of the Art in Credit Scoring by Predicting the Probability That Somebody Will Experience Financial Distress in the Next Two Years.” Kaggle. https://www.kaggle.com/c/GiveMeSomeCredit.
Karimi, Amir-Hossein, Bernhard Schölkopf, and Isabel Valera. 2021. “Algorithmic Recourse: From Counterfactual Explanations to Interventions.” In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, 353–62.
Mothilal, Ramaravind K, Amit Sharma, and Chenhao Tan. 2020. “Explaining Machine Learning Classifiers Through Diverse Counterfactual Explanations.” In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, 607–17.
Pace, R Kelley, and Ronald Barry. 1997. “Sparse Spatial Autoregressions.” Statistics & Probability Letters 33 (3): 291–97.
Pedregosa, Fabian, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, et al. 2011. “Scikit-Learn: Machine Learning in Python.” The Journal of Machine Learning Research 12: 2825–30.
Schut, Lisa, Oscar Key, Rory Mc Grath, Luca Costabello, Bogdan Sacaleanu, Yarin Gal, et al. 2021. “Generating Interpretable Counterfactual Explanations By Implicit Minimisation of Epistemic and Aleatoric Uncertainties.” In International Conference on Artificial Intelligence and Statistics, 1756–64. PMLR.
Upadhyay, Sohini, Shalmali Joshi, and Himabindu Lakkaraju. 2021. “Towards Robust and Reliable Algorithmic Recourse.” https://arxiv.org/abs/2102.13620.
Wachter, Sandra, Brent Mittelstadt, and Chris Russell. 2017. “Counterfactual Explanations Without Opening the Black Box: Automated Decisions and the GDPR.” Harv. JL & Tech. 31: 841.
Yeh, I-Cheng, and Che-hui Lien. 2009. “The Comparisons of Data Mining Techniques for the Predictive Accuracy of Probability of Default of Credit Card Clients.” Expert Systems with Applications 36 (2): 2473–80.